The present invention relates to memory systems, and more particularly, to a method for correcting errors in memories that store multiple bits in each memory cell.
Computer memories typically store data in storage cells that store one bit of data, per storage cell. Each storage cell typically includes a capacitor for storing a charge representing the data bit and a transistor for selectively connecting the storage cell to a bit line during the reading and writing of data into the storage cell. For example, dynamic random-access memories (DRAMs) provide the bulk of the semiconductor-based memories on most computer systems. A DRAM stores data in the form of charge that is stored on a capacitor within the memory cell. The current commercially available DRAMs store one bit in each memory cell, which consists of a transistor and a capacitor. The cost per bit stored is determined by the size of the memory cell. In the past, cost reductions have been achieved primarily by reducing the size of the transistor and capacitor.
A second method for reducing the cost of storage is to utilize memory cells that can store multiple bits per memory cell. To store N bits per memory cell, each memory cell must provide 2N discrete distinguishable states. In general, the states correspond to the charge stored on a capacitor or floating gate. The maximum number of bits that can be stored depends on the sensitivity of the circuits used to measure the stored charge, on the ability of the write circuits to precisely control the amount of charge that is stored on the capacitor, and on the noise level in the bit lines, sense amplifiers, etc. While the problems associated with the precision of the charge storing and read-out circuitry can be overcome with the aid of improved circuitry and reference cells, the problems associated with the noise levels remain. In general, there is some level of noise at which the variations in the measured charge caused by the noise is of the same order as the change in the stored charge obtained by changing the least most significant bit of the data value from a one to a zero in a statistically significant number of memory cells. As the number of bits per storage cell increases, the critical noise level decreases, since the charge difference corresponding to the least most significant bit decreases by a factor of 2 for each additional bit being stored. Hence, prior art multilevel memories have been limited to two or three bits per storage cell.
In principle, an error correcting code can be used to extend the number of bits that can be stored per storage cell. An error correcting code will be defined to be a transformation that maps each possible value of a data word onto a corresponding value in a set of storage words such that errors in storage can be detected and corrected. In general, these codes rely on the fact that only a small number of the possible storage words will be used if no errors are introduced during the storage and retrieval process. For example, in a typical error-correcting code, each 8-bit data word is transformed into a 16-bit storage word. There are only 256 possible data word values; hence, only 256 of the possible 65536 storage word values will be used in the absence of errors. When an error occurs, a valid storage word is usually converted to an invalid storage word. The error correcting system then tries to figure out which valid state would have given rise to the detected invalid state if various numbers of bits were altered by the storage operation.
The ability of an error correcting code to correct errors is measured by a quantity referred to as the xe2x80x9cHamming Distancexe2x80x9d associated with the code. For example, codes with a Hamming Distance of 5 can detect errors resulting from 4 single-bit errors and correct for all possible 2 single-bit errors. A discussion of error correcting codes may be found in ERROR CORRECTING CODES, 2ND EDITION, by Peterson and Weldon, MIT PRESS, 1972, or in PRACTICAL ERROR DESIGN FOR ENGINEERS, by Neil Glover, Data Systems Technology Corp., 1982.
The number of bits in the storage words is always more than the number of bits in the data words. Hence, the use of an error-correcting code may not provide much improvement in the number of bits stored per memory cell. Consider a memory in which each memory cell, in the absence of an error-correcting code, can store 6 bits. That is, the noise levels are sufficiently low that 64 states can be stored and recovered by the sense amplifiers. To store a data word having 24 bits, 4 storage cells are needed. Now, consider the case in which the data is encoded using an error-correcting code in which 8-bit data words are replaced by 16-bit storage words and each memory cell can now store 8-bits with the same error rate after decoding. To store 24 bits of data, the memory must now store three 16-bit storage words at the improved density of 8-bits/memory cell. Hence, the error-correcting code encoded data requires 6 memory cells.
Broadly, it is the object of the present invention to provide an improved multilevel memory.
It is a further object of the present invention to provide a multilevel memory that utilizes an error-correcting code to improve the number of data bits that can be stored per storage cell.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.
The present invention is a memory that stores a plurality of data storage words, each data storage word includes a plurality of data storage cells arranged as a plurality of columns of data storage cells, at least one of the data storage cells storing data specifying a data value having 3 or more states. The memory includes a plurality of data lines, one such data line corresponding to each column of data storage cells, each data storage cell having a gate for connecting that storage cell to the corresponding data line, each data storage cell assuming one of said states in response to a signal on the corresponding data line and a write signal, the state is determined by the signal on the corresponding data line. The memory includes a plurality of data writing circuits, one such data writing circuit corresponding to each data line and being connected to that data line. At least one of the data writing circuits includes a circuit for receiving a digital value having a plurality of bits and for generating a data programming signal on the corresponding data line in response to the write signal. The memory also includes an error encryption circuit for receiving a data word to be stored in the memory and generating therefrom an encrypted data storage word. The encryption circuit divides the encrypted data storage word into a plurality of sub-data storage words, at least one of the sub-data storage words having a plurality of bits and couples each sub-data storage word to a corresponding one of the data writing circuits in response to a write signal being received by the memory. The two least significant bits of the sub-data storage words are encrypted via a first error-encryption algorithm and the most significant bits of the sub-data storage words are either not encrypted or encrypted via a second error encryption algorithm, the second error encryption algorithm having a Hamming Distance that is less than the Hamming Distance of the first error-encryption algorithm. The memory includes a read circuit, responsive to a read signal, for reading out the values stored in the sub-data storage words currently connected to the data lines. The read circuit includes a plurality of sense amplifiers, one such sense amplifier coupled to each data line, each sense amplifier generating an uncorrected sub-data storage word from a signal on that line, at least one of the sub-data storage words includes a plurality of data bits. An error decrypting circuit generates a corrected data word from the uncorrected sub-data storage words. The error decrypting circuit generates an increment or decrement to be added to an uncorrected sub-data storage word to arrive at a correct sub-data storage word value.